package com.hy.treeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TreeNodeLevelOrderByBottom {

    /**
     * 107.二叉树的层次遍历 II
     * 力扣题目链接
     *
     * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     *
     * 思路：
     *
     * 相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。
     *
     *
     */
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    // BFS--迭代方式--借助队列
    public  List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return null;
        }
        queue.offer(root);

        while (!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int len = queue.size();
            while (len > 0){
                // 弹出 元素
                TreeNode node = queue.poll();
                temp.add(node.val);

                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                len --;
            }
            resList.add(temp);
        }

        for (int i = resList.size() - 1; i >= 0; i--) {
            res.add(resList.get(i));
        }
        return res;
    }

/*    //DFS--递归方式
    public void levelOrder2(TreeNode root,Integer deep){
        if (root == null){
            return;
        }
        deep ++;

        //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
        if (resList.size() < deep){
            ArrayList<Integer> item = new ArrayList<>();
            resList.add(item);
        }
        // 添加元素
        resList.get(deep - 1).add(root.val);
        levelOrder2(root.left,deep);
        levelOrder2(root.right, deep);
    }*/






    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeLevelOrderByBottom treeNodeLevelOrder = new TreeNodeLevelOrderByBottom();
        System.out.println("层序遍历: "+treeNodeLevelOrder.levelOrder(root));

    }
}
